This patent includes a Microfiche Appendix which consists of a total of 5 microfiche that contain a total of 442 frames.
The present invention relates generally to the generation of random test data, and more particularly to the generation of such test data as part of a verification programming language.
Random test data has a wide variety of uses. A particularly important application of random test data is in the verification of digital electronic circuits in order to exercise a wide variety of circuit paths for possible faults.
To tackle the increasing complexity of integrated digital electronic circuits, designers need faster and more accurate methods for verifying the functionality and timing of such circuits, particularly in light of the need for ever-shrinking product development times.
The complexity of designing such circuits is often handled by expressing the design in a high-level hardware description language (HLHDL). The HLHDL description is then converted into an actual circuit through a process, well known to those of ordinary skill in the art as xe2x80x9csynthesis,xe2x80x9d involving translation and optimization. Typical examples of an HLHDL are IEEE Standard 1076-1993 VHDL and IEEE Standard 1364-1995 Verilog HDL, both of which are herein incorporated by reference.
An HLHDL description can be verified by simulating the HLHDL description itself, without translating the HLHDL to a lower-level description. This simulation is subjected to certain test data and the simulation""s responses are recorded or analyzed.
Verification of the HLHDL description is important since detecting a circuit problem early prevents the expenditure of valuable designer time on achieving an efficient circuit implementation for a design which, at a higher level, will not achieve its intended purpose. In addition, simulation of the design under test (DUT) can be accomplished much more quickly in an HLHDL than after the DUT has been translated into a lower-level, more circuit oriented, description.
The verification of HLHDL descriptions has been aided through the development of Hardware Verification Languages (or HVLs). Among other goals, HVLs are intended to provide programming constructs and capabilities which are more closely matched to the task of modeling the environment of an HLHDL design than are, for example, the HLHDL itself or software-oriented programming languages (such as C or C++). HVLs permit a DUT, particularly those DUTs expressed in an HLHDL, to be tested by stimulating certain inputs of the DUT and monitoring the resulting states of the DUT.
The present invention adds to Vera capabilities which facilitate the generation of random test data.
In an analogy to classical signal-processing models, Vera provides a xe2x80x9csourcexe2x80x9d of data (random number generation) and the facilities for designing a series of xe2x80x9cfiltersxe2x80x9d (constraints) to transform that data into a form which provides adequate testing.
Sources of random numbers are easily produced by simply adding the randomness attribute xe2x80x9crandxe2x80x9d or xe2x80x9crandcxe2x80x9d to a variable declaration of a class definition. Such variables with a randomness attribute are referred to as xe2x80x9crandom variables.xe2x80x9d
Adding a randomness attribute to a variable declaration permits a class instance containing the variable to make meaningful use of the xe2x80x9crandomizexe2x80x9d method for the generation of random values for those declared variables. A randomize method call causes any random variables of an instance to have a randomly generated value (or values) assigned.
The randomness attribute can be applied to user-defined sub-objects of an instance, as well as to built-in data types. The randomness attribute can be applied to arrays of fixed size or to xe2x80x9cassociative arraysxe2x80x9d of undeclared size.
The values assigned to random variables are controlled using xe2x80x9cconstraint blocks,xe2x80x9d which are part of the class definition. A constraint block is comprised of constraint_expressions, where each constraint_expression limits the values which can be assigned to a random variable which is on the left-hand-side (lhs) of the constraint_expression. The right-hand-side (rhs) of a constraint_expression, in conjunction with a relational operator, is used to derive a range or ranges of permissible values for the lhs random variable.
The introduction of constraint blocks in a class definition permits instances of that class to make meaningful use of the xe2x80x9cconstraint_modexe2x80x9d method. Initially, all constraint blocks of an instance are active or ON, meaning that all the constraint_expressions within the block will act to constrain their lhs random variables. constraint_mode can be used to turn ON or OFF any or all constraint blocks of an instance. A constraint block which is OFF means that all of its constraint_expressions will not act to constrain their lhs random variables.
A constraint_expression can constrain any random variable which has been declared at its level in the class hierarchy, or at any higher level. A constraint_expression cannot constrain a random variable declared at a lower level in the hierarchy. Lower level classes inherit variables and methods from higher level classes.
A single random variable can be constrained by zero or more constraint_expressions, each of which may be in a different constraint block and at a different class hierarchy level. A single random variable may not be constrained by constraint_expressions, however, which present logically inconsistent constraints. Such logical inconsistencies are checked for while performing the randomize method since such xe2x80x9cinconsistenciesxe2x80x9d may dynamically appear, and disappear, under program control. For example, inconsistencies may appear and disappear depending upon which constraint blocks have been enabled with the constraint_mode method. Other possibilities, for controlling the existence of inconsistencies, are values assigned to other random variables during the execution of randomize method, as well as the values assigned to non-random variables before randomize is begun.
Because random variables may appear on the rhs of a constraint_expression, the following complications are handled. A constraint_expression with rhs random variables means that the lhs random variable of the expression xe2x80x9cdepends onxe2x80x9d the rhs random variables for the value which may be chosen. Therefore, there is an implicit ordering in which values must be assigned to random variables: the rhs random variables must be assigned their random values first such that the constraints, which limit the permissible values for the lhs random variable, can be determined. This ordering may continue through several constraint_expressions, since the rhs random variables of one constraint_expression may themselves be lhs random variables of other constraint_expressions which also have random variables on their rhs.
The dependency, of one random variable upon the prior assignment of other random variables, is expressed by means of a directed acyclic graph (or DAG). It is syntactically possible to define a cyclic dependency between random variablesxe2x80x94such cyclic dependencies are detected during DAG construction and are not permitted.
In order to perform the randomize method, a linear ordering must be derived from the DAG or DAGs which may be constructed. The linear ordering is derived such that each random variable is not assigned a value until all random variables which it depends upon (directly or indirectly) for constraining its permissible values have already been assigned values.
The randomize method operates by evaluating the constraint_expressions which are ON according to the linear ordering. For a particular lhs random variable, call it random variable X, its constraint_expressions are translated into a set constraint structure which we shall call Y.
The set_constraint structure Y consists of tuples, called ranges, which specify the valid values which the random variable X can assume. These ranges also have weights associated with them which indicate the relative probability with which a value for X should be selected from that range. The selection of a random value for X, from its set_constraint Y, is basically a two-step process. First, a range within set_constraint Y is randomly chosen, where the likelihood of choosing a particular range is increased by its weight value. Secondly, within the range selected a particular value is randomly selected.
The boundary method operates similarly to the randomize method in that it evaluates the constraint_expressions which are ON according to the linear ordering. For a particular lhs random variable, call it random variable X, its constraint_expressions are translated into a set_constraint structure which we shall call Y.
The set_constraint structure Y consists of tuples, called ranges, which specify the valid values which the random variable X can assume. For boundary, unlike randomize, the weights of these ranges are ignored. The selection of a value for X, from its set_constraint Y, is also performed for boundary according to a different process than utilized in randomize.
Rather than selecting a value for each random variable X from a random point within one of its ranges, as done for randomize, the purpose of boundary is to sequentially select a combination of boundary values, with each boundary value being chosen from a different random variable and the value chosen for each random variable being limited to the boundary values of its ranges which comprise its set_constraint structure. Each range of a set_constraint is defined by a low and a high value; these low and high values of all ranges are the boundary values which the boundary method is limited to selecting. By selecting a boundary value for each random variable of the instance, in a coordinated fashion, all combinations of boundary values can be produced through successive calls to the boundary function. As with randomize, since random variables may depend upon each other, the selection of a boundary value for one random variable may change the selection of boundary values available for other random variables.
Advantages of the invention will be set forth, in part, in the description that follows and, in part, will be understood by those skilled in the art from the description or may be learned by practice of the invention. The advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims and equivalents.